#!/usr/bin/env python
# -*- coding: utf-8 -*-

class Point(object):
	def __init__(self,x,y):
		self.x = float(x)
		self.y = float(y)
	
class SDT():
	def __init__(self,deltaE):
		# deltaE 建议设置为量程的千分之一
		self.currentData = None
		self.lastReadData = None
		self.lastStoredData = None
		self.deltaE = deltaE
		self.resetGate()
	
	def resetGate(self):
		self.up_gate = float("-inf")
		self.down_gate = float("inf")
		
	def check(self,data):
		#print data
		if isinstance(data,tuple) or isinstance(data,tuple):
			self.currentData = Point(data[0],data[1])
		elif isinstance(data,dict):
			self.currentData = Point(data["x"],data["y"])
		else:
			self.currentData = data
			
		if self.lastStoredData==None:
			self.lastStoredData = self.currentData
			return self.lastStoredData.x,self.lastStoredData.y
		if self.lastReadData==None: self.lastReadData = self.currentData
		if self.currentData.x==self.lastStoredData.x: return None,None
		
		now_up = (self.currentData.y - self.lastStoredData.y - self.deltaE)/(self.currentData.x - self.lastStoredData.x)
		now_down = (self.currentData.y - self.lastStoredData.y + self.deltaE)/(self.currentData.x - self.lastStoredData.x)
		if now_up>self.up_gate:
			self.up_gate = now_up
		if now_down<self.down_gate:
			self.down_gate = now_down
		if self.up_gate>=self.down_gate:
			self.lastStoredData = self.lastReadData
			self.lastReadData = self.currentData
			self.up_gate = (self.currentData.y - self.lastStoredData.y - self.deltaE)/(self.currentData.x - self.lastStoredData.x)
			self.down_gate = (self.currentData.y - self.lastStoredData.y + self.deltaE)/(self.currentData.x - self.lastStoredData.x)
			return self.lastStoredData.x,self.lastStoredData.y
		else:
			self.lastReadData = self.currentData
		return None,None

def compress(s,x,y):
	xx=[]
	yy=[]
	for i in range(len(x)):
		xi = x[i]
		yi = y[i]
		dx,dy = s.check((xi,yi))
		if dx!=None and dy!=None:
			xx.append(dx)
			yy.append(dy)
			print "checked (%.2f,%.2f)"%(xi,yi),"stored (%.2f,%.2f)"%(dx,dy),True
		else:
			pass
			#print "checked (%.2f,%.2f)"%(xi,yi),"stored (%s,%s)"%(dx,dy),False
	return xx,yy

if __name__=='__main__':
	import matplotlib.pyplot as plt
	import numpy as np
	import random,math
	deltaE = 10
	x = [0.0, 6.3000000000000007, 12.600000000000001, 18.900000000000002, 25.200000000000003, 31.5, 37.800000000000004, 44.100000000000001, 50.400000000000006, 56.700000000000003, 63.0, 69.300000000000011, 75.600000000000009, 81.900000000000006, 88.200000000000003, 94.5, 100.80000000000001, 107.10000000000001, 113.40000000000001, 119.7, 126.0, 132.30000000000001, 138.60000000000002, 144.90000000000001, 151.20000000000002, 157.5, 163.80000000000001, 170.10000000000002, 176.40000000000001, 182.70000000000002, 189.0, 195.30000000000001, 201.60000000000002, 207.90000000000001, 214.20000000000002, 220.5, 226.80000000000001, 233.10000000000002, 239.40000000000001, 245.70000000000002, 252.0, 258.30000000000001, 264.60000000000002, 270.89999999999998, 277.20000000000005, 283.5, 289.80000000000001, 296.10000000000002, 302.40000000000003, 308.70000000000005, 315.0, 321.30000000000001, 327.60000000000002, 333.90000000000003, 340.20000000000005, 346.5, 352.80000000000001, 359.10000000000002, 365.40000000000003, 371.70000000000005, 378.0, 384.30000000000001, 390.60000000000002]
	y = [0.0, 997.47911776867318, 1883.6306484302829, 2847.1449418851716, 4056.0212388981445, 4570.5200736918168, 5743.7834419804476, 6291.1572637628979, 6775.9467114801137, 8499.2041730252276, 8302.1942231700959, 8257.8702644062905, 9737.0871397412011, 9250.2316047273325, 9726.8886372957859, 9871.6226845342171, 9869.1424242960675, 10129.283119316751, 10261.846846613045, 9299.8711390717926, 8561.4403019255005, 8359.8892051987132, 7938.7139373382406, 7905.4882263044919, 6523.3696933426072, 5949.6127041841673, 5319.4943459243959, 4051.763874363096, 3255.729438440776, 2356.586034263195, 1427.1510615003599, 434.97149984950977, -588.12313491281077, -1614.8755055568629, -2768.31141836404, -3659.645038519689, -4400.8134243047962, -5093.292483946534, -5990.1691826447741, -6868.3008476142913, -7208.3235941020266, -8112.7639821921439, -8788.6299872447526, -9329.6723220727945, -9894.0512604469277, -9300.2331593293384, -10137.566360906694, -10138.791702883274, -9767.0918675533885, -10660.051204937248, -9675.5940210668196, -8856.7917856482454, -9316.1683045331702, -8153.3135842098563, -7649.4146240224227, -6764.8671418353106, -6021.4754189091609, -5903.6801885618943, -4731.7076601347044, -3714.9189997536087, -2577.0439036646558, -1909.1050691982807, -819.7363131514644]
	deltaE = 10.0/1000.0
	x=[0,1,2,3,4,5,6,7,8,9,10,11]
	y=[0,2,-1,3,3,4,2,6,7,5,1,6]
	xx = []
	yy = []
	for i in range(len(x)-1):
		#print i,x[i],y[i]
		x1,y1 = x[i],y[i]
		x2,y2 = x[i+1],y[i+1]
		k = (y2-y1)/float(x2-x1)
		b = y2 - x2*(y2-y1)/float(x2-x1)
		count = 100
		lx = math.fabs(x1-x2)/float(count)
		for di in range(count):
			dx = x1+lx*di
			dy = k*dx + b
			xx.append(dx)
			yy.append(dy)
			#print dx,dy
	scale = 100;flags=[-1,1];deltaE=0.005*scale
	x = np.arange(0,2*np.pi,0.01)
	y = np.sin(x)*scale
	xx = [t for t in x]
	yy = [t+(([-1,1]+[0]*98)[random.randint(0,100)%100])*scale*min(0.02,random.random()) for t in y];#[t+0.1*random.randint(0,int(t*(10*random.random()))) for t in y]
	
	s = SDT(deltaE)
	x = xx
	y = yy
	cx,cy = compress(s,x,y)
	cx.append(x[-1])
	cy.append(y[-1])
	
	plt.grid(True, linewidth = "0.5")
	plt.plot(x,y)
	plt.xlabel("x")
	plt.ylabel("y")
	print len(cx),len(x),float(len(cx))/float(len(x))
	plt.plot(cx,cy,".")
	plt.show()
	